//
// Created by Administrator on 2024/9/2.
// 讲解: https://blog.csdn.net/justidle/article/details/104203958
//
#include <iostream>
#include "arrUtil.h"
using namespace std;

vector<int> merge1(vector<int> a, vector<int> b)
{
    vector<int> ret;
    int i = 0,j=0;
    while (i < a.size() && j < b.size())
    {
        if (a[i]<=b[j])
        {
            ret.push_back(a[i]);
            i++;
        }
        else
        {
            ret.push_back(b[j]);
            j++;
        }
    }
    while(i<a.size())
    {
        ret.push_back(a[i]);
        i++;
    }
    while(j<b.size())
    {
        ret.push_back(b[j]);
        j++;
    }
    return ret;
}

// temp数组是用来临时保存归并后的数据, 最终还要重新赋值回v
// 所以temp作为参数是没必要的, 应该在函数内新建一个数组, 见文件08
void merge2(vector<int> &v, vector<int> temp, int l, int r, int m)
{
//    printf("l:%d, r:%d, m:%d\n",l,r,m);
    int i=l,j=m+1;
    while(i<=m&&j<=r)
    {
        if(v[i]<=v[j])
        {
            temp.push_back(v[i]);
            ++i;
        }
        else
        {
            temp.push_back(v[j]);
            ++j;
        }
    }
    while(i<=m)
    {
        temp.push_back(v[i]);
        ++i;
    }
    while(j<=r)
    {
        temp.push_back(v[j]);
        ++j;
    }
    for (int i = l; i <= r ; ++i)
    {
        v[i]=temp[i-l];
    }
}

void mergeSort(vector<int> &v,vector<int> temp, int l, int r)
{
    if(l<r)
    {
//        int m = l+(r-l)/2;
        int m =(r+l)/2;
        mergeSort(v,temp,l,m);
        mergeSort(v,temp,m+1,r);
        merge2(v,temp,l,r,m);
    }
}

int main()
{
    vector<int> v1{1, 3, 5, 7,8};
    vector<int> v2{3, 4, 6, 9};
    vector<int> v{1,3,5,7,8, 3,4,6,9};
    vector<int> nv = merge1(v1, v2);
//    merge2(v,{},0,v.size()-1,4);
//    printVector(nv);
//    printVector(v);
//    vector<int> v = {0,9,8,7,5,4,3,0,3,2};
    randVector(v,1000);
     mergeSort(v,{},0,v.size()-1);
//    printVector(v);
    cout<<checkSortVector(v);
    return 0;
}